/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/minimum-index-sum-of-two-lists
   @Language: C++
   @Datetime: 19-05-15 11:36
   */

class Solution {
public:
	/**
	 * @param list1: a list of strings
	 * @param list2: a list of strings
	 * @return: the common interest with the least list index sum
	 */
	vector<string> findRestaurant(vector<string> &list1, vector<string> &list2) {
		// Write your code here
		unordered_map<string,int> m1;
		for(int i=list1.size(); i--; m1[list1[i]]=i);
		unordered_map<int,vector<string> > vs;
		int minisum=INT_MAX;
		for(int i=list2.size(), sum; i--;){
			if(m1.count(list2[i])){
				sum=m1[list2[i]]+i;
				minisum=min(minisum,sum);
				vs[sum].push_back(list2[i]);
			}
		}
		return vs[minisum];
	}
};
